package com.leetcode.dfs;

import java.util.HashSet;
import java.util.Set;

public class NumDecodings {
    public static void main(String[] args) {

    }

    public int numDecodings(String s) {
        dfs(s, 0);
        return res;
    }

    Set<String> LegalStr = new HashSet<String>()
    {
        {
            add("1");add("2");add("3");add("4");add("5");add("6");
            add("7");add("8");add("9");add("10");add("11");add("12");
            add("13");add("14");add("15");add("16");add("17");add("18");
            add("19");add("20");add("21");add("22");add("23");add("24");
            add("25");add("26");
        }
    };

    private int res = 0;

    private void dfs(String s, int ind) {
        if (ind == s.length()) {
            res++;
            return;
        }
        if (LegalStr.contains(s.substring(ind, ind + 1))) {
            dfs(s, ind + 1);
        }
        if (s.substring(ind).length() > 1 && LegalStr.contains(s.substring(ind ,ind + 2))) {
            dfs(s, ind + 2);
        }
    }

    private int dp(String s) {
        int n = s.length();
        int[] res = new int[n + 1];
        res[0] = 1;
        for (int i = 1; i <= n; i++) {
            if (s.charAt(i - 1) != '0') {
                res[i] += res[i-1];
            }
            if (i > 1 && s.charAt(i - 2) != '0'
                    && (s.charAt(i-2) - '0') * 10 + (s.charAt(i-1) - '0') <= 26) {
                res[i] += res[i - 2];
            }
        }
        return res[n];
    }
}
